{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #最小跳跃次数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #breadth-first-search #segment-tree #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #广度优先搜索 #线段树 #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minJump"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最小跳跃次数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>为了给刷题的同学一些奖励，力扣团队引入了一个弹簧游戏机。游戏机由 <code>N</code> 个特殊弹簧排成一排，编号为 <code>0</code> 到 <code>N-1</code>。初始有一个小球在编号 <code>0</code> 的弹簧处。若小球在编号为 <code>i</code> 的弹簧处，通过按动弹簧，可以选择把小球向右弹射&nbsp;<code>jump[i]</code> 的距离，或者向左弹射到任意左侧弹簧的位置。也就是说，在编号为 <code>i</code> 弹簧处按动弹簧，小球可以弹向 <code>0</code> 到 <code>i-1</code> 中任意弹簧或者 <code>i+jump[i]</code> 的弹簧（若 <code>i+jump[i]&gt;=N</code> ，则表示小球弹出了机器）。小球位于编号 0 处的弹簧时不能再向左弹。</p>\n",
    "\n",
    "<p>为了获得奖励，你需要将小球弹出机器。请求出最少需要按动多少次弹簧，可以将小球从编号 <code>0</code> 弹簧弹出整个机器，即向右越过编号 <code>N-1</code> 的弹簧。</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<blockquote>\n",
    "<p>输入：<code>jump = [2, 5, 1, 1, 1, 1]</code></p>\n",
    "\n",
    "<p>输出：<code>3</code></p>\n",
    "\n",
    "<p>解释：小 Z 最少需要按动 3 次弹簧，小球依次到达的顺序为 0 -&gt; 2 -&gt; 1 -&gt; 6，最终小球弹出了机器。</p>\n",
    "</blockquote>\n",
    "\n",
    "<p><strong>限制：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= jump.length &lt;= 10^6</code></li>\n",
    "\t<li><code>1 &lt;= jump[i] &lt;= 10000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [zui-xiao-tiao-yue-ci-shu](https://leetcode.cn/problems/zui-xiao-tiao-yue-ci-shu/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [zui-xiao-tiao-yue-ci-shu](https://leetcode.cn/problems/zui-xiao-tiao-yue-ci-shu/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,5,1,1,1,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJump(self, jump: List[int]) -> int:\n",
    "        res = n = len(jump)\n",
    "        dp = [n]*(n+1)\n",
    "        dp[0] = 0\n",
    "        max_dis = [0]*(n+1) \n",
    "        curr_min_num = 0\n",
    "        for i in range(0,n):\n",
    "            if i>max_dis[curr_min_num]:\n",
    "                curr_min_num += 1\n",
    "            dp[i] = min(dp[i],curr_min_num+1)\n",
    "            \n",
    "            j = i+jump[i]\n",
    "            if j>=n:\n",
    "                res = min(res,dp[i]+1)\n",
    "            else:\n",
    "                dp[j] = min(dp[j],dp[i]+1)\n",
    "                max_dis[dp[i]+1] = max(max_dis[dp[i]+1],j)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJump(self, jump: List[int]) -> int:\n",
    "        res = n = len(jump)\n",
    "        f = [n]*(n+1)\n",
    "        f[0] = 0\n",
    "        max_dis = [0]*(n+1) \n",
    "        curr_min_num = 0\n",
    "        for i in range(0,n):\n",
    "            if i>max_dis[curr_min_num]:\n",
    "                curr_min_num += 1\n",
    "                max_dis[curr_min_num] = max(max_dis[curr_min_num], i)\n",
    "            f[i] = min(f[i],curr_min_num+1)\n",
    "            \n",
    "            jump_tmp = i+jump[i]\n",
    "            if jump_tmp>=n:\n",
    "                res = min(res,f[i]+1)\n",
    "            else:\n",
    "                f[jump_tmp] = min(f[jump_tmp],f[i]+1)\n",
    "                max_dis[f[i]+1] = max(max_dis[f[i]+1],jump_tmp)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJump(self, jump: List[int]) -> int:\n",
    "        n = len(jump)\n",
    "        dp = [0] * (n)\n",
    "        dp[-1] = 1\n",
    "        for i in range(n-2, -1,-1):\n",
    "            dp[i] = 1 if i + jump[i] >= n else dp[i + jump[i]] + 1\n",
    "            for j in range(i + 1,n):\n",
    "                if dp[j] < dp[i] + 1:\n",
    "                    break\n",
    "                dp[j] = dp[i] + 1\n",
    "\n",
    "        return dp[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJump(self, jump: List[int]) -> int:\n",
    "        dp = [0] * len(jump)\n",
    "        for i in range(len(jump)-1,-1,-1):\n",
    "            if i + jump[i] >= len(jump):\n",
    "                dp[i] = 1\n",
    "            else:\n",
    "                dp[i] = 1 + dp[i + jump[i]]\n",
    "            for j in range(i+1,len(jump)): # 因为后面可以往前跳，所以往后遍历一次把后面次数过大的替换掉\n",
    "                if dp[j] <= dp[i]: # 当出现这种情况，下标比j还大的后面的就可以选择从j跳了，因此不用再从i跳\n",
    "                    break\n",
    "                else:\n",
    "                    dp[j] = dp[i] + 1\n",
    "        return dp[0]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJump(self, jump: List[int]) -> int:\n",
    "        res = n = len(jump)\n",
    "        f = [n]*(n+1)\n",
    "        f[0] = 0\n",
    "        max_dis = [0]*(n+1) \n",
    "        curr_min_num = 0\n",
    "        for i in range(0,n):\n",
    "            if i>max_dis[curr_min_num]:\n",
    "                curr_min_num += 1\n",
    "            f[i] = min(f[i],curr_min_num+1)\n",
    "            \n",
    "            jump_tmp = i+jump[i]\n",
    "            if jump_tmp>=n:\n",
    "                res = min(res,f[i]+1)\n",
    "            else:\n",
    "                f[jump_tmp] = min(f[jump_tmp],f[i]+1)\n",
    "                max_dis[f[i]+1] = max(max_dis[f[i]+1],jump_tmp)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJump(self, jump: List[int]) -> int:\n",
    "        res = n = len(jump)\n",
    "        f = [n]*(n+1)\n",
    "        f[0] = 0\n",
    "        max_dis = [0]*(n+1) \n",
    "        curr_min_num = 0\n",
    "        for i in range(0,n):\n",
    "            if i>max_dis[curr_min_num]:\n",
    "                curr_min_num += 1\n",
    "            f[i] = min(f[i],curr_min_num+1)\n",
    "            \n",
    "            jump_tmp = i+jump[i]\n",
    "            if jump_tmp>=n:\n",
    "                res = min(res,f[i]+1)\n",
    "            else:\n",
    "                f[jump_tmp] = min(f[jump_tmp],f[i]+1)\n",
    "                max_dis[f[i]+1] = max(max_dis[f[i]+1],jump_tmp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJump(self, jump: List[int]) -> int:\n",
    "        n = len(jump)\n",
    "        dp = [0] * n\n",
    "        dp[-1] = 1\n",
    "        for i in range(n-2, -1, -1):\n",
    "            if i+jump[i] >= n:\n",
    "                dp[i] = 1\n",
    "            else:\n",
    "                dp[i] = dp[i+jump[i]] + 1\n",
    "            for j in range(i+1, n):\n",
    "                if dp[j] >= dp[i] + 1:\n",
    "                    dp[j] = dp[i] + 1\n",
    "                else:\n",
    "                    break\n",
    "            # print(dp)\n",
    "        return dp[0]\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJump(self, jump: List[int]) -> int:\n",
    "        res = n = len(jump)\n",
    "        f = [n]*(n+1)\n",
    "        f[0] = 0\n",
    "        max_dis = [0]*(n+1) \n",
    "        curr_min_num = 0\n",
    "        for i in range(0,n):\n",
    "            if i>max_dis[curr_min_num]:\n",
    "                curr_min_num += 1\n",
    "            f[i] = min(f[i],curr_min_num+1)\n",
    "            \n",
    "            jump_tmp = i+jump[i]\n",
    "            if jump_tmp>=n:\n",
    "                res = min(res,f[i]+1)\n",
    "            else:\n",
    "                f[jump_tmp] = min(f[jump_tmp],f[i]+1)\n",
    "                max_dis[f[i]+1] = max(max_dis[f[i]+1],jump_tmp)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minJump(self, jump: List[int]) -> int:\n",
    "        minstep = [0 for i in range(len(jump))]\n",
    "        for i in range(len(jump) - 1, -1, -1):\n",
    "            minstep[i] = minstep[i + jump[i]] + 1 if (i + jump[i]) < len(jump) else 1\n",
    "            for j in range(1, jump[i]):\n",
    "                if (i+j) >= len(jump):\n",
    "                    break\n",
    "                if minstep[i+j] >= (minstep[i] + 1):\n",
    "                    minstep[i + j] = minstep[i] + 1\n",
    "                else:\n",
    "                    break\n",
    "        return minstep[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJump(self, jump: List[int]) -> int:\n",
    "        res = n = len(jump)\n",
    "        f = [n]*(n+1)\n",
    "        f[0] = 0\n",
    "        max_dis = [0]*(n+1) \n",
    "        curr_min_num = 0\n",
    "        for i in range(0,n):\n",
    "            if i>max_dis[curr_min_num]:\n",
    "                curr_min_num += 1\n",
    "            f[i] = min(f[i],curr_min_num+1)\n",
    "            \n",
    "            jump_tmp = i+jump[i]\n",
    "            if jump_tmp>=n:\n",
    "                res = min(res,f[i]+1)\n",
    "            else:\n",
    "                f[jump_tmp] = min(f[jump_tmp],f[i]+1)\n",
    "                max_dis[f[i]+1] = max(max_dis[f[i]+1],jump_tmp)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJump(self, jump: List[int]) -> int:\n",
    "        res = n = len(jump)\n",
    "        f = [n]*(n+1)\n",
    "        f[0] = 0\n",
    "        max_dis = [0]*(n+1) \n",
    "        curr_min_num = 0\n",
    "        for i in range(0,n):\n",
    "            if i>max_dis[curr_min_num]:\n",
    "                curr_min_num += 1\n",
    "            f[i] = min(f[i],curr_min_num+1)\n",
    "            \n",
    "            jump_tmp = i+jump[i]\n",
    "            if jump_tmp>=n:\n",
    "                res = min(res,f[i]+1)\n",
    "            else:\n",
    "                f[jump_tmp] = min(f[jump_tmp],f[i]+1)\n",
    "                max_dis[f[i]+1] = max(max_dis[f[i]+1],jump_tmp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJump(self, jump: List[int]) -> int:\n",
    "        res = n = len(jump)\n",
    "        f = [n]*(n+1)\n",
    "        f[0] = 0\n",
    "        max_dis = [0]*(n+1) \n",
    "        curr_min_num = 0\n",
    "        for i in range(0,n):\n",
    "            if i>max_dis[curr_min_num]:\n",
    "                curr_min_num += 1\n",
    "            f[i] = min(f[i],curr_min_num+1)\n",
    "            \n",
    "            jump_tmp = i+jump[i]\n",
    "            if jump_tmp>=n:\n",
    "                res = min(res,f[i]+1)\n",
    "            else:\n",
    "                f[jump_tmp] = min(f[jump_tmp],f[i]+1)\n",
    "                max_dis[f[i]+1] = max(max_dis[f[i]+1],jump_tmp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJump(self, jump: List[int]) -> int:\n",
    "        res = n = len(jump)\n",
    "        f = [n] * (n + 1)\n",
    "        f[0] = 0\n",
    "        maxDis = [0] * (n + 1)\n",
    "        currMinNum = 0\n",
    "        for i in range(n):\n",
    "            if i > maxDis[currMinNum]:\n",
    "                currMinNum += 1\n",
    "            f[i] = min(f[i], currMinNum + 1)\n",
    "\n",
    "            jumpTmp = i + jump[i]\n",
    "            if jumpTmp >= n:\n",
    "                res = min(res, f[i] + 1)\n",
    "            else:\n",
    "                f[jumpTmp] = min(f[jumpTmp], f[i] + 1)\n",
    "                maxDis[f[i] + 1] = max(maxDis[f[i] + 1], jumpTmp)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJump(self, jump: List[int]) -> int:\n",
    "        res = n = len(jump)\n",
    "        f = [n]*(n+1)\n",
    "        f[0] = 0\n",
    "        max_dis = [0]*(n+1) \n",
    "        curr_min_num = 0\n",
    "        for i in range(0,n):\n",
    "            if i>max_dis[curr_min_num]:\n",
    "                curr_min_num += 1\n",
    "            f[i] = min(f[i],curr_min_num+1)\n",
    "            \n",
    "            jump_tmp = i+jump[i]\n",
    "            if jump_tmp>=n:\n",
    "                res = min(res,f[i]+1)\n",
    "            else:\n",
    "                f[jump_tmp] = min(f[jump_tmp],f[i]+1)\n",
    "                max_dis[f[i]+1] = max(max_dis[f[i]+1],jump_tmp)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJump(self, jump: List[int]) -> int:\n",
    "        N = len(jump)\n",
    "        dp = [float(\"inf\")]*(N+1)\n",
    "        dp[0] = 0\n",
    "        maxPos = 0 \n",
    "        cnt = 0\n",
    "        mapMaxRight={}\n",
    "        mapMaxRight[0]=0\n",
    "        minCnt = 0\n",
    "        for i in range(N):\n",
    "            njump = min(jump[i]+i,N)\n",
    "            # print(heap,mapMaxRight)\n",
    "            dp[i] = min(dp[i],minCnt+1)  \n",
    "            dp[njump] = min(dp[njump],dp[i]+1)\n",
    "            if dp[njump] not in mapMaxRight:\n",
    "                mapMaxRight[dp[njump]] = njump\n",
    "            else:\n",
    "                mapMaxRight[dp[njump]] = max(njump,mapMaxRight[dp[njump]])\n",
    "            if mapMaxRight[minCnt] == i:\n",
    "                minCnt+=1\n",
    "                \n",
    "        # print(dp)\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJump(self, jump: List[int]) -> int:\n",
    "        n = len(jump)\n",
    "        q = deque([(0,1)])\n",
    "        visit = [False] * n\n",
    "        visit[0] = True\n",
    "        index = 0\n",
    "        while q:\n",
    "            T,d = q.popleft()\n",
    "            if T + jump[T] >= n:\n",
    "                return d\n",
    "            while True:\n",
    "                while index < n and visit[index]:\n",
    "                    index += 1\n",
    "                if index > T:\n",
    "                    break\n",
    "                visit[index] = True\n",
    "                q.append((index,d + 1))\n",
    "            if not visit[T + jump[T]]:\n",
    "                visit[T + jump[T]] = True\n",
    "                q.append((T + jump[T],d + 1))\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJump(self, jump: List[int]) -> int:\n",
    "            L=len(jump)\n",
    "            dp=[0]*L\n",
    "            dp[-1]=1\n",
    "\n",
    "            for i in range(L-2,-1,-1):\n",
    "                if jump[i]+i>=L: dp[i]=1\n",
    "                else:dp[i]=dp[jump[i]+i]+1\n",
    "                for j in range(i+1,L):\n",
    "                    if dp[j]<dp[i]+1:break\n",
    "                    dp[j]=dp[i]+1\n",
    "                    \n",
    "            return dp[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJump(self, jump: List[int]) -> int:\n",
    "            L=len(jump)\n",
    "            dp=[0]*L\n",
    "            dp[-1]=1\n",
    "\n",
    "            for i in range(L-2,-1,-1):\n",
    "                if jump[i]+i>=L: dp[i]=1\n",
    "                else:dp[i]=dp[jump[i]+i]+1\n",
    "                for j in range(i+1,L):\n",
    "                    if dp[j]<dp[i]+1:break\n",
    "                    dp[j]=dp[i]+1\n",
    "                    \n",
    "            return dp[0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJump(self, jump: List[int]) -> int:\n",
    "        N = len(jump)\n",
    "        dp = [float(\"inf\")]*(N+1)\n",
    "        dp[0] = 0\n",
    "        maxPos = 0 \n",
    "        cnt = 0\n",
    "        mapMaxRight = {}\n",
    "        mapMaxRight[0]=0\n",
    "        heap = [0]\n",
    "        for i in range(N):\n",
    "            njump = min(jump[i]+i,N)\n",
    "            # print(heap,mapMaxRight)\n",
    "            minJump = heap[0]\n",
    "            if mapMaxRight[minJump] <= i:\n",
    "                heapq.heappop(heap)\n",
    "    \n",
    "            dp[i] = min(dp[i],minJump+1)\n",
    "            dp[njump] = min(dp[njump],dp[i]+1)\n",
    "            if dp[njump] not in mapMaxRight:\n",
    "                heapq.heappush(heap,dp[njump])\n",
    "                mapMaxRight[dp[njump]] = njump\n",
    "            mapMaxRight[dp[njump]] = max(njump,mapMaxRight[dp[njump]])\n",
    "\n",
    "        # print(dp)\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJump(self , jump: List[int]) -> int:\n",
    "        # write code here\n",
    "        N = len(jump)\n",
    "        visited = [False] * N\n",
    "        dui = collections.deque()\n",
    "        dui.append([0,0])\n",
    "        visited[0] = True\n",
    "        pre = 1\n",
    "        while dui:\n",
    "            idx,d = dui.popleft()\n",
    "            next = idx + jump[idx]\n",
    "            if next >= N:\n",
    "                return d + 1\n",
    "            else:\n",
    "                if not visited[next]:\n",
    "                    visited[next] = True \n",
    "                    dui.append([next,d+1])\n",
    "                for i in range(pre,idx):\n",
    "                    if not visited[i]:\n",
    "                        visited[i] = True \n",
    "                        dui.append([i,d+1])\n",
    "                pre = idx\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJump(self, jump: List[int]) -> int:\n",
    "        n = len(jump)\n",
    "\n",
    "        dp = [inf] * (2 * n + 1)\n",
    "        dp[0] = 0\n",
    "\n",
    "        que = deque()\n",
    "        que.append(0)\n",
    "\n",
    "        while que:\n",
    "            u = que.popleft()\n",
    "\n",
    "            if u == 2 * n:\n",
    "                break\n",
    "\n",
    "            if u < n:\n",
    "                if u + jump[u] >= n:\n",
    "                    if dp[2 * n] > dp[u] + 1:\n",
    "                        dp[2 * n] = dp[u] + 1\n",
    "                        que.append(2 * n)\n",
    "                elif dp[u + jump[u]] > dp[u] + 1:\n",
    "                    dp[u + jump[u]] = dp[u] + 1\n",
    "                    que.append(u + jump[u])\n",
    "                \n",
    "                if dp[u + n] > dp[u] + 1:\n",
    "                    dp[u + n] = dp[u] + 1\n",
    "                    que.append(u + n)\n",
    "\n",
    "            else:\n",
    "                if dp[u - n] > dp[u]:\n",
    "                    dp[u - n] = dp[u]\n",
    "                    que.appendleft(u - n)\n",
    "                \n",
    "                if u > n and dp[u - 1] > dp[u]:\n",
    "                    dp[u - 1] = dp[u]\n",
    "                    que.appendleft(u - 1)\n",
    "\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "差分数组：维护区间最小值\n",
    "'''\n",
    "class Solution:\n",
    "    def minJump(self, jump: List[int]) -> int:\n",
    "        n = len(jump)\n",
    "        if jump[0] >= n:\n",
    "            return 1\n",
    "\n",
    "        step = [inf] * (n + 1)\n",
    "        step[0] = 0\n",
    "        #had[0][0]:表示到had[0][1]的最小步数是had[0][0]\n",
    "        had = [(1, jump[0])]\n",
    "        step[jump[0]] = 1\n",
    "\n",
    "        ans = inf\n",
    "        for i in range(1, n):\n",
    "            while had and had[0][1] < i:\n",
    "                heapq.heappop(had)\n",
    "\n",
    "            if had:   \n",
    "                pre = had[0][1]    \n",
    "                step[i] = min(step[i], step[pre] + 1)\n",
    "\n",
    "            if i + jump[i] >= n:\n",
    "                ans = min(ans, step[i] + 1)\n",
    "            else:\n",
    "                j = i + jump[i]  \n",
    "                if step[i] + 1 < step[j]:\n",
    "                    step[j] = step[i] + 1\n",
    "                    heapq.heappush(had, (step[j], j))\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJump(self, jump: List[int]) -> int:\n",
    "        dp = [0] * len(jump)\n",
    "        for i in range(len(jump)-1,-1,-1):\n",
    "            if i + jump[i] >= len(jump):\n",
    "                dp[i] = 1\n",
    "            else:\n",
    "                dp[i] = 1 + dp[i + jump[i]]\n",
    "            for j in range(i+1,len(jump)): # 因为后面可以往前跳，所以往后遍历一次把后面次数过大的替换掉\n",
    "                if dp[j] <= dp[i]: # 当出现这种情况，下标比j还大的后面的就可以选择从j跳了，因此不用再从i跳\n",
    "                    break\n",
    "                else:\n",
    "                    dp[j] = dp[i] + 1\n",
    "        return dp[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "差分数组：维护区间最小值\n",
    "'''\n",
    "class Solution:\n",
    "    def minJump(self, jump: List[int]) -> int:\n",
    "        n = len(jump)\n",
    "        if jump[0] >= n:\n",
    "            return 1\n",
    "\n",
    "        step = [inf] * (n + 1)\n",
    "        step[0] = 0\n",
    "        #had[0][0]:表示到had[0][1]的最小步数是had[0][0]\n",
    "        had = [(1, jump[0])]\n",
    "        step[jump[0]] = 1\n",
    "\n",
    "        ans = inf\n",
    "        for i in range(1, n):\n",
    "            while had and had[0][1] < i:\n",
    "                heapq.heappop(had)\n",
    "            if had:    \n",
    "                pre = had[0][1]    \n",
    "                step[i] = min(step[i], step[pre] + 1)\n",
    "\n",
    "            if i + jump[i] >= n:\n",
    "                ans = min(ans, step[i] + 1)\n",
    "            else:\n",
    "                j = i + jump[i]  \n",
    "                if step[i] + 1 < step[j]:\n",
    "                    step[j] = step[i] + 1\n",
    "                    heapq.heappush(had, (step[j], j))\n",
    "\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJump(self, jump: List[int]) -> int:\n",
    "            L=len(jump)\n",
    "            dp=[0]*L\n",
    "            dp[-1]=1\n",
    "\n",
    "            for i in range(L-2,-1,-1):\n",
    "                if jump[i]+i>=L: dp[i]=1\n",
    "                else:dp[i]=dp[jump[i]+i]+1\n",
    "                for j in range(i+1,L):\n",
    "                    if dp[j]<dp[i]+1:break\n",
    "                    dp[j]=dp[i]+1\n",
    "                    \n",
    "            return dp[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJump(self, jump: List[int]) -> int:\n",
    "        n = len(jump)\n",
    "        dp = [0] * n\n",
    "        dp[-1] = 1\n",
    "        for i in range(n-2, -1, -1):\n",
    "            if i+jump[i] >= n:\n",
    "                dp[i] = 1\n",
    "            else:\n",
    "                dp[i] = dp[i+jump[i]] + 1\n",
    "            for j in range(i+1, n):\n",
    "                if dp[j] >= dp[i] + 1:\n",
    "                    dp[j] = dp[i] + 1\n",
    "                else:\n",
    "                    break\n",
    "        return dp[0]\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJump(self, jump: List[int]) -> int:\n",
    "        res = n = len(jump)\n",
    "        f = [n]*(n+1)\n",
    "        f[0] = 0\n",
    "        max_dis = [0]*(n+1) \n",
    "        curr_min_num = 0\n",
    "        for i in range(0,n):\n",
    "            if i>max_dis[curr_min_num]:\n",
    "                curr_min_num += 1\n",
    "            f[i] = min(f[i],curr_min_num+1)\n",
    "            \n",
    "            jump_tmp = i+jump[i]\n",
    "            if jump_tmp>=n:\n",
    "                res = min(res,f[i]+1)\n",
    "            else:\n",
    "                f[jump_tmp] = min(f[jump_tmp],f[i]+1)\n",
    "                max_dis[f[i]+1] = max(max_dis[f[i]+1],jump_tmp)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJump(self, jump: List[int]) -> int:\n",
    "        res = n = len(jump)\n",
    "        f = [n] * (n + 1)\n",
    "        f[0] = 0\n",
    "        max_dis = [0] * (n + 1)\n",
    "        curr_min_num = 0\n",
    "\n",
    "        for i in range(0, n):\n",
    "            if i > max_dis[curr_min_num]:\n",
    "                curr_min_num += 1\n",
    "            f[i] = min(f[i], curr_min_num + 1)\n",
    "\n",
    "            jump_tmp = i + jump[i]\n",
    "\n",
    "            if jump_tmp >= n:\n",
    "                res = min(res, f[i] + 1)\n",
    "            else:\n",
    "                f[jump_tmp] = min(f[jump_tmp], f[i] + 1)\n",
    "                max_dis[f[i] + 1] = max(max_dis[f[i] + 1], jump_tmp)\n",
    "        return res  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJump(self, jump: List[int]) -> int:\n",
    "            L=len(jump)\n",
    "            dp=[0]*L\n",
    "            dp[-1]=1\n",
    "\n",
    "            # 倒着思考，从最后能到的算为1步\n",
    "            for i in range(L-2,-1,-1):\n",
    "                if jump[i]+i>=L: dp[i]=1\n",
    "                else:dp[i]=dp[jump[i]+i]+1\n",
    "                for j in range(i+1,L):\n",
    "                    # 如果遍历到某dp[j]<dp[i]+1就不需要向右遍历了,因为j到dp.length的值会被当前遍历到的dp[j]更新而不是dp[i]+1\n",
    "                    if dp[j]<dp[i]+1:break\n",
    "                    dp[j]=dp[i]+1\n",
    "                    \n",
    "            return dp[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJump(self, jump: List[int]) -> int:\n",
    "        q = deque()\n",
    "        sz = len(jump)\n",
    "        st = [False] * sz\n",
    "        q.append((0, 0))\n",
    "        st[0] = True\n",
    "        left = 0\n",
    "\n",
    "        while q:\n",
    "            idx, step = q.popleft()\n",
    "\n",
    "            right = idx + jump[idx]\n",
    "            if right >= sz:\n",
    "                return step + 1\n",
    "            \n",
    "            if not st[right]:\n",
    "                st[right] = True\n",
    "                q.append((right, step + 1))\n",
    "            \n",
    "            if idx > left:\n",
    "                for i in range(left+1, idx):\n",
    "                    if not st[i]:\n",
    "                        st[i] = True\n",
    "                        q.append((i, step + 1))\n",
    "                left = idx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJump(self, jump: List[int]) -> int:\n",
    "        # pre = collections.defaultdict(list)\n",
    "        n = len(jump)\n",
    "        dp = [0] * (n + 1)\n",
    "        for i in range(n-1, -1, -1):\n",
    "            if i + jump[i] >= n:\n",
    "                dp[i] = 1\n",
    "            else:\n",
    "                dp[i] = dp[i + jump[i]] + 1\n",
    "            for k in range(i+1, n):\n",
    "                if dp[k] < dp[i] + 1:\n",
    "                    break\n",
    "                dp[k] = dp[i] + 1\n",
    "        return dp[0]\n",
    "        # for i in range(n-1, -1, -1):\n",
    "        #     t = min(n, i + jump[i])\n",
    "        #     pre[t].append(i)\n",
    "        # q = collections.deque()\n",
    "        # r = n\n",
    "        # q.append(n)\n",
    "        # while q:\n",
    "        #     v = q.popleft()\n",
    "        #     for u in pre[v]:\n",
    "        #         if dp[u] == 0:\n",
    "        #             dp[u] = dp[v] + 1\n",
    "        #             q.append(u)\n",
    "        #         else:\n",
    "        #             # dp[u] = min(dp[u], dp[v] + 1)\n",
    "        #             if dp[v] + 1 < dp[u]:\n",
    "        #                 dp[u] = dp[v] + 1\n",
    "        #                 q.append(u)\n",
    "        #         for x in range(u+1, r):\n",
    "        #             if dp[x] == 0:\n",
    "        #                 dp[x] = dp[v] + 2\n",
    "        #                 q.append(x)\n",
    "        #             else:\n",
    "        #                 # dp[x] = min(dp[x], dp[v] + 2)\n",
    "        #                 if dp[v] + 2 < dp[x]:\n",
    "        #                     dp[x] = dp[v] + 2\n",
    "        #                     q.append(x)\n",
    "        #         r = min(u, r)\n",
    "        # print(dp)\n",
    "        # return dp[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJump(self, jump: List[int]) -> int:\n",
    "        dp = [0] * len(jump)\n",
    "        for i in range(len(jump)-1,-1,-1):\n",
    "            if i + jump[i] >= len(jump):\n",
    "                dp[i] = 1\n",
    "            else:\n",
    "                dp[i] = 1 + dp[i + jump[i]]\n",
    "            for j in range(i+1,len(jump)): # 因为后面可以往前跳，所以往后遍历一次把后面次数过大的替换掉\n",
    "                if dp[j] <= dp[i]: # 当出现这种情况，下标比j还大的后面的就可以选择从j跳了，因此不用再从i跳\n",
    "                    break\n",
    "                else:\n",
    "                    dp[j] = dp[i] + 1\n",
    "        return dp[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJump(self, jump: List[int]) -> int:\n",
    "        n = len(jump)\n",
    "        first = 1\n",
    "\n",
    "        for i in range(n-1, -1, -1):\n",
    "            if i+jump[i]>=n:\n",
    "                jump[i] = 0\n",
    "                first = i\n",
    "\n",
    "        for i in range(first-1, -1, -1):\n",
    "            if i+jump[i]>=first:\n",
    "                jump[i] = min(3, jump[i+jump[i]]+2)\n",
    "            else:\n",
    "                jump[i] = 1+jump[i+jump[i]]\n",
    "            \n",
    "            for j in range(i+1, n):\n",
    "                if jump[j]<=jump[i]:\n",
    "                    break\n",
    "                jump[j] = jump[i]+1\n",
    "\n",
    "        return jump[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJump(self, jump: List[int]) -> int:\n",
    "        n = jump.__len__()\n",
    "        q = deque()\n",
    "        q.appendleft((0, 0))\n",
    "        \n",
    "        i = 1\n",
    "        x = set()\n",
    "\n",
    "        while q:\n",
    "            pos, times = q.popleft()\n",
    "            n_pos = pos + jump[pos]\n",
    "            if n_pos >= n:\n",
    "                return times + 1\n",
    "            if n_pos not in x:\n",
    "                q.append((n_pos, times+1))\n",
    "                x.add(n_pos)\n",
    "            \n",
    "            while i < pos:\n",
    "                q.append((i, times+1))\n",
    "                i += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJump(self, jump: List[int]) -> int:\n",
    "        n = jump.__len__()\n",
    "        q = deque()\n",
    "        q.appendleft((0, 0))\n",
    "        \n",
    "        i = 1\n",
    "        x = set()\n",
    "\n",
    "        while q:\n",
    "            pos, times = q.popleft()\n",
    "            n_pos = pos + jump[pos]\n",
    "            if n_pos >= n:\n",
    "                return times + 1\n",
    "            if n_pos not in x:\n",
    "                q.append((n_pos, times+1))\n",
    "                x.add(n_pos)\n",
    "            \n",
    "            while i < pos:\n",
    "                q.append((i, times+1))\n",
    "                i += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, val=0, next=None) -> None:\n",
    "        self.next = next \n",
    "        self.val = val \n",
    "\n",
    "            \n",
    "class Solution:\n",
    "    def minJump(self, jump: List[int]) -> int:\n",
    "        n = jump.__len__()\n",
    "        q = deque()\n",
    "        \n",
    "        tail = head = Node((0, 0))\n",
    "        q.appendleft((0, 0))\n",
    "        \n",
    "        i = 1\n",
    "        x = set()\n",
    "\n",
    "        while True:\n",
    "            pos, times = head.val\n",
    "            n_pos = pos + jump[pos]\n",
    "            if n_pos >= n:\n",
    "                return times + 1\n",
    "            if n_pos not in x:\n",
    "                tail.next = Node((n_pos, times+1))\n",
    "                tail = tail.next\n",
    "                x.add(n_pos)\n",
    "            \n",
    "            while i < pos:\n",
    "                tail.next = Node((i, times+1))\n",
    "                tail = tail.next\n",
    "                i += 1\n",
    "            head = head.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, val=0, next=None) -> None:\n",
    "        self.next = next \n",
    "        self.val = val \n",
    "\n",
    "            \n",
    "class Solution:\n",
    "    def minJump(self, jump: List[int]) -> int:\n",
    "        n = jump.__len__()\n",
    "        q = deque()\n",
    "        \n",
    "        tail = head = Node((0, 0))\n",
    "        q.appendleft((0, 0))\n",
    "        \n",
    "        i = 1\n",
    "        x = set()\n",
    "\n",
    "        while True:\n",
    "            pos, times = head.val\n",
    "            n_pos = pos + jump[pos]\n",
    "            if n_pos >= n:\n",
    "                return times + 1\n",
    "            if n_pos not in x:\n",
    "                tail.next = Node((n_pos, times+1))\n",
    "                tail = tail.next\n",
    "                x.add(n_pos)\n",
    "            \n",
    "            while i < pos:\n",
    "                tail.next = Node((i, times+1))\n",
    "                tail = tail.next\n",
    "                i += 1\n",
    "            head = head.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJump(self, jump: List[int]) -> int:\n",
    "        n=len(jump)\n",
    "        que=[0]\n",
    "        dep=0\n",
    "        l=0\n",
    "        nxti=0\n",
    "        seen=[0]*n\n",
    "        while que:\n",
    "            nxt=[]\n",
    "            while que:\n",
    "                i=que.pop()\n",
    "                nxti=i+jump[i]\n",
    "                nxt.append(nxti)\n",
    "                if nxti>=n:\n",
    "                    return dep+1\n",
    "                if i>l:\n",
    "                    for j in range(l+1,i):\n",
    "                        if not seen[j]:\n",
    "                            nxt.append(j)\n",
    "                            seen[i]=1\n",
    "                    l=i\n",
    "                \n",
    "            \n",
    "            que=nxt\n",
    "            dep+=1\n",
    "            # print(dep,que)\n",
    "    \n",
    "                    \n",
    "                    \n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJump(self, jump):\n",
    "        res = n = len(jump)\n",
    "        visited = [False]*(n+1)\n",
    "        queue = [[0,1]]\n",
    "        visited[0] = True\n",
    "        curr, far = 0, 1\n",
    "        while curr<len(queue):\n",
    "            idx, step = queue[curr][0], queue[curr][1]\n",
    "            curr += 1\n",
    "            if idx + jump[idx] >= n:\n",
    "                return step\n",
    "            if not visited[idx+jump[idx]]:\n",
    "                queue.append([idx+jump[idx], step+1])\n",
    "                visited[idx+jump[idx]] = True\n",
    "            for j in range(far, idx):\n",
    "                if not visited[j]:\n",
    "                    queue.append([j, step+1])\n",
    "                    visited[j] = True\n",
    "            far = max(far, idx+1)\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJump(self, jump):\n",
    "        res = n = len(jump)\n",
    "        visited = [False]*(n+1)\n",
    "        queue = [[0,1]]\n",
    "        visited[0] = True\n",
    "        curr, far = 0, 1\n",
    "        while curr<len(queue):\n",
    "            idx, step = queue[curr][0], queue[curr][1]\n",
    "            curr += 1\n",
    "            if idx + jump[idx] >= n:\n",
    "                return step\n",
    "            if not visited[idx+jump[idx]]:\n",
    "                queue.append([idx+jump[idx], step+1])\n",
    "                visited[idx+jump[idx]] = True\n",
    "            for j in range(far, idx):\n",
    "                if not visited[j]:\n",
    "                    queue.append([j, step+1])\n",
    "                    visited[j] = True\n",
    "            far = max(far, idx+1)\n",
    "        return -1\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
